package main

func main() {
	// [144. 二叉树的前序遍历](https://leetcode.cn/problems/binary-tree-preorder-traversal/)
	// [94. 二叉树的中序遍历](https://leetcode.cn/problems/binary-tree-inorder-traversal/)
	// [145. 二叉树的后序遍历](https://leetcode.cn/problems/binary-tree-postorder-traversal/)
	// [102. 二叉树的层序遍历](https://leetcode.cn/problems/binary-tree-level-order-traversal/)
}

// 144
func preorderTraversal(root *TreeNode) []int {
	//递归
	ans := make([]int, 0)
	var preorder func(*TreeNode)
	preorder = func(node *TreeNode) {
		if node == nil {
			return
		}
		ans = append(ans, node.Val)
		preorder(node.Left)
		preorder(node.Right)
	}
	preorder(root)
	return ans
	//迭代
	stack := make([]*TreeNode, 0)
	ans := make([]int, 0)
	node := root
	for node != nil || len(stack) > 0 {
		for node != nil {
			ans = append(ans, node.Val)
			stack = append(stack, node)
			node = node.Left
		}
		node = stack[len(stack)-1].Right
		stack = stack[:len(stack)-1]
	}
	return ans
}

// 94
func inorderTraversal(root *TreeNode) []int {
	//递归
	var inorder func(*TreeNode)
	ans := make([]int, 0)
	inorder = func(node *TreeNode) {
		if node == nil {
			return
		}
		inorder(node.Left)
		ans = append(ans, node.Val)
		inorder(node.Right)
	}
	inorder(root)
	return ans
	//迭代
	stack := make([]*TreeNode, 0)
	ans := make([]int, 0)
	for root != nil || len(stack) > 0 {
		for root != nil {
			stack = append(stack, root)
			root = root.Left
		}
		root = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		ans = append(ans, root.Val)
		root = root.Right
	}
	return ans
}

// 145
func postorderTraversal(root *TreeNode) []int {
	//递归
	var postorder func(*TreeNode)
	ans := make([]int, 0)
	postorder = func(node *TreeNode) {
		if node == nil {
			return
		}
		postorder(node.Left)
		postorder(node.Right)
		ans = append(ans, node.Val)
	}
	postorder(root)
	return ans
	//迭代
	stack := make([]*TreeNode, 0)
	ans := make([]int, 0)
	var per *TreeNode
	for root != nil || len(stack) > 0 {
		for root != nil {
			stack = append(stack, root)
			root = root.Left
		}
		root = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		if root.Right == nil || root.Right == per {
			ans = append(ans, root.Val)
			per = root
			root = nil
		} else {
			stack = append(stack, root)
			root = root.Right
		}
	}
	return ans
}

// 102
func levelOrder(root *TreeNode) [][]int {
	queue := make([]*TreeNode, 0)
	ans := make([][]int, 0)
	if root != nil {
		queue = append(queue, root)
	}
	for len(queue) > 0 {
		size := len(queue)
		tmp := make([]int, 0)
		for i := 0; i < size; i++ {
			node := queue[0]
			queue = queue[1:]
			tmp = append(tmp, node.Val)
			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
			}
		}
		ans = append(ans, tmp)
	}
	return ans
}
